package LeetCode刷题;

import java.util.HashMap;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-23 19:08
 * @description: Functions of this class is
 * 牛客版本：
 * private class LRUNode{
 *         int key;
 *         int value;
 *         LRUNode next;
 *         LRUNode pre;
 *         public LRUNode(){}
 *         public LRUNode(int key,int value){
 *             this.key=key;
 *             this.value=value;
 *         }
 *     }
 *     private int capacity;
 *     private int size;
 *     private HashMap<Integer,LRUNode> cache=new HashMap<Integer,LRUNode>();
 *     private LRUNode head;
 *     private LRUNode tail;
 *     public int[] LRU (int[][] operators, int k) {
 *         // write code here
 *         //若opt=1，接下来两个整数key, value，表示set(key, value)
 *         //若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
 *         this.capacity=k;
 *         head=new LRUNode();
 *         tail=new LRUNode();
 *         head.next=tail;
 *         tail.pre=head;
 *         int len=operators.length;
 *         List<Integer> list=new ArrayList();
 *         for(int i=0;i<len;i++){
 *             switch(operators[i][0]){
 *                 case 1:{
 *                     //若opt=1，接下来两个整数key, value，表示set(key, value)
 *                     set(operators[i][1],operators[i][2]);
 *                     break;
 *                 }
 *                 case 2:{
 *                     //若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
 *                     list.add(get(operators[i][1]));
 *                 }
 *             }
 *         }
 *         len=list.size();
 *         int ans[]=new int[len];
 *         for(int i=0;i<len;i++){
 *             ans[i]=list.get(i);
 *         }
 *         return ans;
 *     }
 *     private void addtoHead(LRUNode node){
 *         node.next=head.next;
 *         head.next.pre=node;
 *         head.next=node;
 *         node.pre=head;
 *     }
 *     private void deleteNode(LRUNode node){
 *         node.pre.next=node.next;
 *         node.next.pre=node.pre;
 *     }
 *     private void removeToHead(LRUNode node){
 *         deleteNode(node);
 *         addtoHead(node);
 *     }
 *     private LRUNode deleteTailNode(){
 *         LRUNode t=tail.pre;
 *         deleteNode(t);
 *         return t;
 *     }
 *     private void set(int key,int value){
 *         LRUNode node=cache.get(key);
 *         if(node!=null){
 *             node.value=value;
 *             cache.put(key,node);
 *             removeToHead(node);
 *         }
 *         else{
 *             LRUNode newNode=new LRUNode(key,value);
 *             cache.put(key,newNode);
 *             addtoHead(newNode);
 *             ++size;
 *             if(size>capacity){
 *                 LRUNode t=deleteTailNode();
 *                 cache.remove(t.key);
 *                 --size;
 *             }
 *         }
 *     }
 *     private int get(int key){
 *         LRUNode node=cache.get(key);
 *         if(node!=null){
 *             removeToHead(node);
 *             return node.value;
 *         }
 *         return -1;
 *     }
 *
 * 该题所要求的数据结构要求为：查找快，插入快，删除快，有顺序之分。
 * *****************************每次进行”增加“或者“删除”操作的时候，都要记得将哈希表和双向链表同步进行操作
 **/
public class NoNoLRU缓存机制 {
    class LRUCache {
        private class LRUNode{
            private int key;
            private int value;
            LRUNode next;
            LRUNode prev;
            public LRUNode(){}
            public LRUNode(int key,int value){
                this.key=key;
                this.value=value;
            }
        }
        private HashMap<Integer,LRUNode> cache=new HashMap<Integer,LRUNode>();
        private int capacity;
        private int size;
        private LRUNode head;//定义为当前LRU缓存队列的头结点
        private LRUNode tail;//定义为当前LRU缓存队列的尾结点

        /**
         * 最容易出错的地方！
         * @param node
         */
        private void addToHead(LRUNode node){//该函数用于将新增节点插入到双向链表头部
            node.next=head.next;
            head.next.prev=node;
            node.prev=head;
            head.next=node;
        }
        private void removeNode(LRUNode node){//该函数用于删除节点
            node.prev.next=node.next;
            node.next.prev=node.prev;
        }
        private void moveToHead(LRUNode node){//该函数用于将当前节点的缓存位置更新，即从原来的位置插入到队头
            removeNode(node);//先删除原来的位置，
            addToHead(node);//再将该节点插入到队头中
        }
        private LRUNode removeTailNode(){//该函数用于删除队尾的节点
            LRUNode t=tail.prev;//找到当前尾部的元素
            removeNode(t);//将其删除
            return t;//同时返回删除了的元素
        }
        public LRUCache(int capacity) {
            //构造方法 初始化一些数据
            this.capacity=capacity;//初始化最大容量
            this.size=0;//初始化开始容量

            //初始化头节点，和尾部节点
            head=new LRUNode();
            tail=new LRUNode();
            head.next=tail;
            tail.prev=head;
        }

        public int get(int key) {
            LRUNode node=cache.get(key);
            if(node!=null){
                moveToHead(node);
                return node.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            LRUNode node=cache.get(key);
            if(node!=null){//说明当前key已经存在了，要进行更新操作
                node.value=value;
                moveToHead(node);//然后更新当前节点的位置，将其放入到队头
            }
            else{//否则要进行新元素插入，这个时候就要判断是否队列已经满了

                LRUNode newNode=new LRUNode(key,value); //创建一个新节点
                cache.put(key,newNode);//进行插入哈希表和双向链表，同时更新其位置
                addToHead(newNode);
                ++size;
                if(size>capacity){//说明已经达到了内存的限制
                    LRUNode t=removeTailNode();//这个时候就要删除当前使用最少的元素，同时取出删除的元素，将其在哈希表中的位置也删除掉
                    cache.remove(t.key);
                    --size;
                }
            }
        }
    }

}